package now_coder.dp.solutions;

public class NCSolution83 {

    /*
     * 子数组最大乘积
     *
     * 给定一个数组 arr，返回这个数组累乘的最大乘积，这个数组中的元素有正有负。我们还是使用 dp[i] 表示以 arr[i] 结尾的
     * 子数组的最大乘积，dp[i] = max(dp[i - 1] * arr[i], arr[i])，但是当遇到负数时，先前最小的元素乘以负数会变成最大，
     * 而之前最大的元素乘以负数会变成最小。比如对于数组：[0.1, 0, 3.0, -2.0, 0.9, -1.3, 5.0, -4.4]
     *
     * 因此，可以生成两个数组 min 和 max：
     *
     * 1.当 arr[i] > 0 时:
     *      max[i] = max(arr[i], max[i - 1] * arr[i])
     *      min[i] = min(arr[i], min[i - 1] * arr[i])
     * 2.当 arr[i] < 0 时：
     *      max[i] = max(arr[i], min[i - 1] * arr[i])
     *      min[i] = max(arr[i], max[i - 1] * arr[i])
     */

}
